package com.fanshuai2.test;

import java.util.*;

/**
 * 给定一个整数数组和一个整数k，你需要找到该数组中和为k的连续的子数组的个数。
 *
 * 示例 1 :
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2 ,
 * 解释：[1,1] 与 [1,1] 为两种不同的情况，所以有两个满足条件的子数组。
 *
 * 示例 2 :
 * 输入:nums = [1,-1,3,1,1,2], k = 2
 * 输出: 3
 * 解释：满足条件的子数组为[-1,3] , [1,1], [2]
 */
public class Sumk {

    static int sumK(int[] arr, int k) {
        int count = 0;

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int sumArr = 0;
        for (int i = 0; i < arr.length; i++) {
            sumArr += arr[i];

            count +=  map.getOrDefault(sumArr - k, 0);
            map.put(sumArr, map.getOrDefault(sumArr, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,1};
        System.out.println(sumK(arr, 2));

        int[] arr1 = {1,-1,3,1,1,2};
        System.out.println(sumK(arr1, 2));
    }
}
